package C052;

/**
 * ClassName: C03
 * Package: C052
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/3/24 00:17
 * @Version 1.0
 * @Since 1.0
 */
public class C03 {
    static int MAXLEN = 30001, r, n;
    static int[][] res = new int[30001][2];
    //static int[] arr = new int[30001];
    public static int MOD = 1000000007;
    static int[] stack = new int[30001];
    public static void main(String[] args) {
        int[] arr = {71,55,82,55};
        System.out.println(sumSubarrayMins(arr));
        System.out.println(MOD);
    }

    // 单调栈题目
    public static int sumSubarrayMins(int[] arr) {
        if(arr.length == 0) {
            return arr[0];
        }
        r = 0;
        n = arr.length;
        int pop;
        for (int i = 0; i < n; i++) {
            while(r > 0 && arr[i] < arr[stack[r - 1]]) {
                pop = stack[--r];
                res[pop][1] = i;
                res[pop][0] = r == 0 ? -1 : stack[r - 1];
            }
            stack[r++] = i;
        }
        // 处理栈剩余的内容
        while(r > 0) {
            pop = stack[--r];
            res[pop][0] = r == 0 ? -1 :  stack[r - 1];
            res[pop][1] = n;
        }

        // 精确校验
//        for (int i = 0; i < n; i++) {
//            while(res[i][0] != -1 && arr[res[i][0]] == arr[i]) {
//                res[i][0] = res[res[i][0]][0];
//            }
//        }

        long result = 0;
        for (int i = 0; i < n; i++) {
            result += (long) (i - res[i][0]) * (res[i][1] - i) * arr[i];
            result %=  (MOD);
        }
        return (int) result;
    }
}
